#include "Solution.h"
#include <algorithm>
#include <iostream>
#include <stack>
#include <map>



void Solution::Test()
{
    vector<int> nums{-1,2,1,-4,-999,999,555};
    cout<<threeSumClosest(nums,555)<<endl;
    auto vs = letterCombinations("2345");
    for(int i = 0; i < vs.size();i++)
    {
        cout<<vs[i]<<endl;
    }
    vector<int> nums1{1, 0, -1, 0, -2, 2,999,-999,555,-555};
	auto vrt = fourSum(nums1,0);
	for(auto it = vrt.begin(); it != vrt.end();it++)
	{
		for(auto iter = (*it).begin(); iter != (*it).end();iter++)
		{
			cout<<*iter<<" ";
		}
		cout<<endl;
	}
	if (isValid("(("))
	{
		cout <<"true"  << endl;
	}
	else
	{
		cout << "false" << endl;
	}
    auto vst = generateParenthesis(4);
	for(auto it = vst.begin(); it != vst.end();it++)
	{
		cout<<*it<<" ";
		cout<<endl;
	}

    
    vector<int> nums2{0,0,1,1,1,2,2,2,3,3,4,4,4,4,4,5};
    for(int i = 0 ; i < nums2.size();i++)
    {
        cout<<"search:"<<search(nums2,i)<<endl;
        auto vv = searchRange(nums2,0);
        cout<<"searchRange:"<<vv[0]<<","<<vv[1]<<endl;
    }
    vector<int> nums3{1,3,6,9};
    for(int i = 0 ; i < nums3.size() ;i++)
    {
        cout<<"i="<<i<<"\tsearchInsert:"<<searchInsert(nums3,9)<<endl;
    }
	
	vector<vector<char>> board{
		{'5','3','.','.','7','.','.','.','.'},
		{'6','.','.','1','9','5','.','.','.'},
		{'.','9','8','.','.','.','.','6','.'},
		{'8','.','.','.','6','.','.','.','3'},
		{'4','.','.','8','.','3','.','.','1'},
		{'7','.','.','.','2','.','.','.','6'},
		{'.','6','.','.','.','.','2','8','.'},
		{'.','.','.','4','1','9','.','.','5'},
		{'.','.','.','.','8','.','.','7','9'}};
		
	//vector<vector<char>> board;
	solveSudoku(board);
	for (auto it = board.begin(); it != board.end(); it++)
	{
		for (auto var : *it)
		{
			cout << var << " ";
		}
		cout << endl;
	}
	for (size_t i = 0; i <= 30; i++)
	{
		cout << countAndSay(i) << endl;
	}
    vector<int> candidates{14,6,25,9,30,20,33,34,28,30,16,12,31,9,9,12,34,16,25,32,8,7,30,12,33,20,21,29,24,17,27,34,11,17,30,6,32,21,27,17,16,8,24,12,12,28,11,33,10,32,22,13,34,18,12};
    auto result = combinationSum2(candidates,27);
    for(auto r :result)
    {
        for(auto nu:r)
            cout<<nu<<" ";
        cout<<endl;
    }
    vector<int> height{ 2,1,2,6,9,7,5,5,7,9,10,20,3,29,0,0,0,1};
    cout<<"接水量为："<<trap(height)<<endl;
    cout<<"multiply:"<<multiply("2","3")<<endl;
    cout<<"multiply:"<<multiply("89898329321312312","88")<<endl;
    cout<<"isMatch:"<<isMatch("aabbccb","a*cb*")<<endl;
	vector<int> numsjump{ 3,2,1,0,4 };
	cout << "jump:" << jump(numsjump) << endl;
	/*
    vector<int> per{ 2,0,0,1,1,3,3};
	auto vvs = permuteUnique(per);
	map<int, int> count;
	for (auto value : vvs)
	{
		int num = 0;
		for (auto val : value)
		{
			num *= 10;
			num += val;
			cout << val << " ";
		}
		count[num]++;
		cout <<"\t"<< count[num] << endl;
	}
	for (auto kv: count)
	{
		cout << kv.first << "\t" << kv.second << endl;
	}

	vector<vector<int>> matrix{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
    rotate(matrix);
    solveNQueens(6);
	vector<int> nnn{ -2,1,-3,-4,-1,-2,1,-5,-4 };
	cout << maxSubArray(nnn) << endl;
    */

    vector<string> wordList{"si","go","se","cm","so","ph","mt","db","mb","sb","kr","ln","tm","le","av","sm","ar","ci","ca","br","ti","ba","to","ra","fa","yo","ow","sn","ya","cr","po","fe","ho","ma","re","or","rn","au","ur","rh","sr","tc","lt","lo","as","fr","nb","yb","if","pb","ge","th","pm","rb","sh","co","ga","li","ha","hz","no","bi","di","hi","qa","pi","os","uh","wm","an","me","mo","na","la","st","er","sc","ne","mn","mi","am","ex","pt","io","be","fm","ta","tb","ni","mr","pa","he","lr","sq","ye"};
    auto retw = findLadders("qa","sq",wordList);
    for(auto wl : retw )
    {
        for(auto s : wl)
        {
            cout<<s<<" ";
        }
        cout<<endl;
    }
    {
        auto result1 = partition("abcba");
        for(auto wl : result1)
        {
            for(auto s : wl)
            {
                cout<<s <<" ";
            }
            cout<<endl;
        }
    }
//    ["X","O","X","O","X","O","O","O","X","O"],
//    ["X","O","O","X","X","X","O","O","O","X"],
//    ["O","O","O","O","O","O","O","O","X","X"],
//    ["O","O","O","O","O","O","X","O","O","X"],
//    ["O","O","X","X","O","X","X","O","O","O"],
//    ["X","O","O","X","X","X","O","X","X","O"],
//    ["X","O","X","O","O","X","X","O","X","O"],
//    ["X","X","O","X","X","O","X","O","O","X"],
//    ["O","O","O","O","X","O","X","O","X","O"],
//    ["X","X","O","X","X","X","X","O","O","O"]]
}

//给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
//找出 nums 中的三个整数，使得它们的和与 target 最接近。
//返回这三个数的和。
//假定每组输入只存在唯一答案。
//输入：nums = [-1,2,1,-4], target = 1
//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
int Solution::threeSumClosest(vector<int>& nums, int target)
{
    sort(nums.begin(),nums.end());
    int n = nums.size();
    int ret = 1e7;
    auto update = [&](int cur)
    {
        if(abs(cur - target) < abs(ret - target))
            ret = cur;
    };

    for(int i = 0 ; i < n;i++)
    {
        if(i > 0 && nums[i] == nums[i - 1])
            continue;
        int p = i + 1;
        int q = n - 1;
        while(p < q)
        {
            auto sum = nums[i] + nums[p] + nums[q];
            if(sum == target)
                return target;
            update(sum);
            if(sum > target)
            {
                while(1)
                {
                    q--;
                    if(nums[q] != nums[q+1])
                        break;
                }
            }
            else
            {
                while(1)
                {
                    p++;
                    if(nums[p] != nums[p-1])
                        break;
                }
            }
        }
    }
    return ret;
}
const char maps[9][4] = {
    {},
    {'a','b','c'},
    {'d','e','f'},
    {'g','h','i'},
    {'j','k','l'},
    {'m','n','o'},
    {'p','q','r','s'},
    {'t','u','v'},
    {'w','x','y','z'}
};

void fun(int i,string str,int n,vector<string>& last,string digits)
{
    cout<<i<<":"<<str<<":"<<n<<endl;
    if(i >= n)
        return;
    int index = digits.at(i) - '1';
    for(int j = 0; j < 4;j++)
    {
        if(maps[index][j] == 0)
        {
            continue;
        }
        string strtmp(str);
        strtmp.append(1,maps[index][j]);
        if(i == n -1 )
        {
            last.push_back(strtmp);
        }
        else
        {
            fun(i+1,strtmp,n,last,digits);
        }
    }
}


vector<string> Solution::letterCombinations(string digits)
{
    const int n = digits.length();
    vector<string> last;

    /*
    for(int i = 0 ; i < n;i++)
    {
        int index = digits.at(i) - '1';
        vector<string> tmp;
        for(int j = 0 ;j < 4;j++)
        {
            if(maps[index][j] == 0)
            {
                continue;
            }
            if(last.empty())
            {
                string str ;
                str.append(1,maps[index][j]);
                tmp.push_back(str);
            }
            else
            {
                for(int k = 0; k < last.size();k++)
                {
                    string str = last[k];
                    str.append(1,maps[index][j]);
                    tmp.push_back(str);
                }
            }
        }
        last = tmp;
    }
    */
    fun(0,"",n,last,digits);
    return last;
}

//删除链表的倒数第N个节点
ListNode* Solution::removeNthFromEnd(ListNode* head, int n)
{
	if (n == 0)
		return nullptr;
	ListNode* end = head;
	ListNode* del = nullptr;
	for (size_t i = 0; i < n; i++)
	{
		if (end == nullptr)
		{
			break;
		}
		end = end->next;
	}
	del = head;
	if (end == nullptr)
	{
		head = head->next;
		delete del;
		return head;
	}
	ListNode* last = nullptr;
	while (end != nullptr)
	{
		last = del;
		del = del->next;
		end = end->next;
	}
	if (last == nullptr)
	{
		return nullptr;
	}
	last->next = del->next;
	delete del;
	return head;
}
ListNode* Solution::mergeTwoLists(ListNode* l1, ListNode* l2)
{
    /* 递归法
    if(l1 == nullptr)
        return l2;
    else if(l2 == nullptr)
        return l1;
    else if(l1->val < l2->val)
    {
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;
    }
    else
    {
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
    return nullptr;
    */
    //迭代法
    ListNode* result = new ListNode(-1);
    ListNode* cur = result;
    while(l1 != nullptr && l2 != nullptr)
    {
        if(l1->val < l2->val )
        {
            cur->next = l1;
            l1 = l1->next;
        }
        else
        {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = l1 != nullptr ? l1 : l2;
    return result->next;
}

void generate(string str,int beg,int end,int open,int close ,vector<string>& res)
{
    if( beg  == end - 1)
    {
        string strs(str);
        strs.append(1,')');
        res.push_back(strs);
        return;
    }
    if(open < end/2)
    {
        str.push_back('(');
        generate(str,beg+1,end,open+1,close,res);
        str.pop_back();
    }
    if(close < open)
    {
        str.push_back(')');
        generate(str,beg+1,end,open,close+1,res);
        str.pop_back();
    }

}

ListNode* merage(vector<ListNode*>& lists,int beg,int end)
{
    if(beg == end)
        return lists[beg];
    return Solution::mergeTwoLists(merage(lists,beg,beg+(end-beg)/2),merage(lists,beg+(end-beg)/2+1,end));
}
ListNode* Solution::mergeKLists(vector<ListNode*>& lists)
{
    if(lists.size() == 0)
        return nullptr;
    return merage(lists,0,lists.size()-1);
}

ListNode* Solution::swapPairs(ListNode* head)
{
    if(!head || !head->next)
        return head;
    ListNode* cur = head; 
    ListNode* next = cur->next;
    head = next;
    ListNode* father = nullptr;
    while(next)
    {
        if(father)
            father->next = next;
        cur->next = next->next;
        next->next = cur;
        father = cur; 
        cur = cur->next;
        if(cur == nullptr)
            break;
        next = cur->next;
    }
    return head;
}
//链表逆序
ListNode* reverse(ListNode* head, ListNode* tail)
{
	ListNode* cur = head;
	while (cur != tail && cur->next != tail)
	{
		ListNode* next = cur->next;
		cur->next = next->next;
		next->next = head;
		head = next;
	}
	return head;
}
ListNode* Solution::reverseKGroup(ListNode* head, int k)
{
	ListNode* cur = head;
	ListNode* beg = head;
	ListNode* tail = NULL;
	int i = 0;
	while (cur)
	{
		if (i == k)
		{
			i = 0;
			ListNode* next = reverse(beg, cur);
			printf("%d=%d\n", next->val, beg->val);
			if (tail == NULL)
			{
				head->next = cur;
				tail = head;
				head = next;
			}
			else
			{
				beg->next = cur;
				tail->next = next;
				tail = beg;
			}
			beg = cur;
		}
		i++;
		cur = cur->next;
	}
	return head;
    return head;
}

vector<string> Solution::generateParenthesis(int n)
{
    vector<string> res;
    generate("",0,2*n,0,0,res);
    return res;
}
//有效的括号
bool Solution::isValid(string s)
{
	int len = s.length();
    if(len == 0)
        return true;
    if(len % 2 != 0)
        return false;
    char array[len/2 + 1];
    int index = 0;
    for(int i = 0;i < len;i++ )
    {
        if(index > len/2)
            return false;
        switch(s.at(i))
        {
            case '}':
                {
                    if(index == 0 ||  array[index-1] != '{')
                        return false;
                    index--;
                }
                break;
            case ']':
                {
                    if(index == 0 || array[index-1] != '[')
                        return false;
                    index--;
                }
                break;
            case ')':
                {
                    if(index == 0 || array[index-1] != '(')
                        return false;
                    index--;
                }
                break;
            case '(':
            case '[':
            case '{':
                {
                    array[index] = s.at(i);
                    index++;
                }
                break;
            default:
                break;
        }
    }
    return index == 0;
}

vector<vector<int>> Solution::fourSum(vector<int>& nums, int target)
{
    vector<vector<int>> ret;

    if(nums.size() < 4)
        return ret;


    sort(nums.begin(),nums.end());
    int len = nums.size();
    if(4 * nums[len - 1] < target 
       || 4 * nums[0] > target)
        return ret; 


    int head = 0;           
    while(head < len - 3)
    {
        if(nums[head] * 4 > target)
            break;
        int tail = len -1;
        while(tail > head + 2)
        {
            if(4 * nums[tail] < target)
                break;
            int second = head + 1;
            int three = tail - 1;
            while(second < three)
            {
                if(nums[head] + nums[second] + nums[three] + nums[tail]  == target)
                {
                    vector<int> tmp;
                    tmp.push_back(nums[head]);
                    tmp.push_back(nums[second]);
                    tmp.push_back(nums[three]);
                    tmp.push_back(nums[tail]);
                    ret.push_back(tmp);
                    while(second < three)
                    {
                        second++;
                        if(nums[second] != nums[second-1])
                            break;
                    }
                }
                else if(nums[head] + nums[second] + nums[three] + nums[tail] > target)
                {
                    while(second < three)
                    {
						three--;
                        if(nums[three] != nums[three+1])
                            break;
                    }
                }
                else
                {	
					while(second < three)
                    {
                        second++;
                        if(nums[second] != nums[second-1])
                            break;
                    }

                }
            }
			while(tail > head + 2)
			{
				tail--;
				if(nums[tail] != nums[tail+1])
					break;
			}
		}
		while(head < len - 3)
		{
			head++;
			if(nums[head] != nums[head-1])
				break;
		}
	}
    return ret;
}
//26.删除排序数组中的重复项
int Solution::removeDuplicates(vector<int>& nums)
{
	if (nums.size() < 2)
		return nums.size();
	int sum = 1;
	for (int i = 1; i < nums.size(); i++)
	{
		if (nums[i] != nums[i - 1])
		{
			nums[sum] = nums[i];
			sum++;
		}
	}
	printf("%d", sum);
	return sum;
}
//27. 移除元素
int Solution::removeElement(vector<int>& nums, int val)
{
	int len = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		if (nums[i] != val)
		{
			nums[len++] = nums[i];
		}
	}
	return len;
}
//28. 实现 strStr()
int Solution::strStr(string haystack, string needle)
{
	auto len = haystack.size();
	int j = 0;
	int find = -1;
	int max = needle.size();
	if (max == 0)
		return  0;
	for (auto i = 0; i < len; i++)
	{
		if (j >= max)
			return find;
		if (haystack[i] == needle[j])
		{
			if (j == 0)
				find = i;
			j++;
		}
		else {
			if (find != -1)
				i = find;
			find = -1;
			j = 0;
		}
	}
	if (j >= max)
		return  find;
	return -1;
}
//29. 两数相除
int mydiv(long a, long b) 
{ 
	if (a < b) return 0;
	long count = 1;
	long tb = b; // 在后面的代码中不更新b
	while ((tb << 1) <= a)
	{
		tb = tb << 1; 
		count = count << 1;
	}
	return count + mydiv(a - tb, b);
}
int Solution::divide(int dividend, int divisor)
{
	if (dividend == 0) 
		return 0;
	if (divisor == 1) 
		return dividend;
	if (divisor == -1) 
	{
		if (dividend > INT_MIN) 
			return -dividend;// 只要不是最小的那个整数，都是直接返回相反数就好啦
		return INT_MAX;// 是最小的那个，那就返回最大的整数啦
	}
	long a = dividend;
	long b = divisor;
	int sign = 1;
	if ((a > 0 && b < 0) || (a < 0 && b>0)) 
	{
		sign = -1;
	}
	a = a > 0 ? a : -a;
	b = b > 0 ? b : -b;
	long res = mydiv(a, b);
	if (sign > 0)
		return res > INT_MAX ? INT_MAX : res;
	return -res;
}
//30. 串联所有单词的子串

vector<int> Solution::findSubstring(string s, vector<string>& words)
{/*
	if (s.empty() || words.empty())
	{
		return {};
	}
	vector<int> result;
	int one_word = words[0].size();
	int word_num = words.size();
	if (s.length() < one_word * word_num)
		return result;
	unordered_map<string, int> m1;
	for (const auto& word : words)
	{
		m1[word]++;
	}
	for (size_t i = 0; i <= s.length() - one_word * word_num; i++)
	{
		auto m2 = m1;
		bool find = true;
		for ( int j = 0; j < one_word * word_num;j += one_word)
		{
			string strtemp = s.substr(i+j, one_word);
			m2[strtemp]--;
			if (m2[strtemp] < 0)
			{
				find = false;
				break;
			}
		}
		if (find)
			result.push_back(i);
	}
	return result;
	*/
	if (words.size() == 0) return {};
	unordered_map<string, int> wordcnt;
	for (auto& w : words) {
		wordcnt[w]++;
	}
	int len = words[0].size();

	vector<int> ans;
	for (int i = 0; i < len; i++) {
		int left = i;
		int right = left;
		int cnt = 0;

		unordered_map<string, int> window;
		while (left + words.size() * len <= s.size()) {
			string temp = "";
			while (cnt < words.size()) {
				temp = s.substr(right, len);
				if (wordcnt.find(temp) == wordcnt.end() || window[temp] >= wordcnt[temp]) break;
				window[temp]++;
				cnt++;
				right += len;
			}

			if (window == wordcnt) {
				ans.push_back(left);
			}

			if (wordcnt.find(temp) != wordcnt.end()) {
				window[s.substr(left, len)]--;
				cnt--;
				left += len;
			}
			else {
				right += len;
				left = right;
				cnt = 0;
				window.clear();
			}
		}
	}
	return ans;
}
